//
//  Problem516.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/7.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 516. 最长回文子序列 【动态规划】【回文】【删除子字符】【字符串】
 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

 示例 1:
     输入:    "bbbab"
     输出:    4
    一个可能的最长回文子序列为 "bbbb"。

 示例 2:
    输入:     "cbbd"
    输出:     2
    一个可能的最长回文子序列为 "bb"。
 
 提示：
     1 <= s.length <= 1000
     s 只包含小写英文字母
 */
@objcMembers class Problem516: NSObject {
    func solution() {
        print(longestPalindromeSubseq("bbbab"))
        print(longestPalindromeSubseq("cbbd"))
    }
    
    /*
     动态规划
     1：创建一个二维数组 dp[len][len]
     2: dp[i][j]:表示 i～j的最长回文长度
     3: dp[i][j] =
        3.1 s[i] == s[j]：那么这2个字符肯定是最长回文的边界 = dp[i+1][j-1] + 2
        3.2 s[i] != s[j]：那么最长回文的边界不能同时是s[i]和s[j]
            3.2.1 s[i] 有可能是左边界，而且s[j]肯定不是右边界 = dp[i][j-1]
            3.2.2 s[j] 有可能是右边界，而且s[i]肯定不是左边界 = dp[i+1][j]
            = max(dp[i][j-1], dp[i+1][j])
     
     */
    func longestPalindromeSubseq(_ s: String) -> Int {
        if s.count == 1 {
            return 1
        }
        
        
        let chars = Array(s)
        var dp = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
        
        let value = longestPalindromeSubseqDP(chars, &dp, 0, s.count - 1)
        for i in 0..<s.count {
            print(dp[i])
        }
        return value
    }
    
    func longestPalindromeSubseqDP(_ chars: [Character], _ dp: inout [[Int]], _ start: Int, _ end: Int) -> Int {
        if start > end {        // 超出边界了
            return 0
        } else if start == end {
            dp[start][end] = 1
            return dp[start][end]
        }
        
        
        if dp[start][end] != -1 {
            return dp[start][end]
        }
        
        if chars[start] == chars[end] {
            dp[start][end] = longestPalindromeSubseqDP(chars, &dp, start + 1, end - 1) + 2
        } else {
            dp[start][end] = max(longestPalindromeSubseqDP(chars, &dp, start + 1, end), longestPalindromeSubseqDP(chars, &dp, start, end - 1))
        }
        
        return dp[start][end]
    }
}
